高精度加法 - 415. 字符串相加

Problem: 415. 字符串相加

思路

高精度加法

解题过程

使用一个字符串ans来保存结果，整数carry保存进位，剩下的就是普通的高精度加法了：

1. 反转字符串，好计算

2. 给两个字符串后添0

3. for i, 1 -> num1.size()循环枚举每个位

• 用一个sum存储相加的和

• carry更新进位，ans添加一个新位

4. 把ans反转回来

复杂度

• 时间复杂度: $O(max(N,M))$$O(\max(N, M))$

• 空间复杂度: $O(max(N,M))$$O(\max(N, M))$

Code

C++

xxxxxxxxxx
class Solution {
public:
    string addStrings(string num1, string num2) {
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        if (num1.size() < num2.size()) {
            num1 += string(num2.size() - num1.size(), '0');
        } else {
            num2 += string(num1.size() - num2.size(), '0');
        }
        string ans;
        int carry = 0;
        for (int i = 0; i < num1.size(); i++) {
            int sum = (num1[i] - '0') + (num2[i] - '0') + carry;
            ans += sum % 10 + '0';
            carry = sum / 10;
        }
        if (carry != 0) {
            ans += carry + '0';
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Python

xxxxxxxxxx
class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        num1 = num1[::-1]
        num2 = num2[::-1]
        if len(num1) < len(num2):
            num1 += '0' * (len(num2) - len(num1))
        else:
            num2 += '0' * (len(num1) - len(num2))
        ans = ""
        carry = 0
        for i in range(len(num1)):
            _sum = (ord(num1[i]) - ord('0')) + (ord(num2[i]) - ord('0')) + carry
            ans += chr(_sum % 10 + ord('0'))
            carry = _sum // 10
        if carry != 0:
            ans += chr(carry + ord('0'))
        ans = ans[::-1]
        return ans

C#

xxxxxxxxxx
public class Solution {
    public string AddStrings(string num1, string num2) {
        if (num1.Length < num2.Length) {
            num1 = new string('0', num2.Length - num1.Length) + num1;
        } else {
            num2 = new string('0', num1.Length - num2.Length) + num2;
        }
        char[] a = num1.ToCharArray();
        Array.Reverse(a);
        char[] b = num2.ToCharArray();
        Array.Reverse(b);
        StringBuilder ans = new StringBuilder();
        int carry = 0;
        for (int i = 0; i < a.Length; i++) {
            int sum = (a[i] - '0') + (b[i] - '0') + carry;
            ans.Append((char)(sum % 10 + '0'));
            carry = sum / 10;
        }
        if (carry != 0) {
            ans.Append((char)(carry + '0'));
        }
        char[] Ans = ans.ToString().ToCharArray();
        Array.Reverse(Ans);
        return new string(Ans);
    }
}